#include <iostream>
#include <limits.h>
using namespace std;
/**
 * 归并排序的时间复杂度为nlgn
 * 归并排序并不是一种原地排序，因为需要额外的申请空间来充当临时容器
 * 归并排序是一种稳定排序
 * **/
void Merge(int A[],int p, int q, int r){
    int i,j,k;
    int n1 = q-p+1;
    int n2 = r-q;
    int *L = new int[n1+1];
    int *R = new int[n2+1];
    for(i = 0; i < n1; i++){
        L[i] = A[i+p];
    }
    for(j = 0; j < n2; j++){
        R[j] = A[j+q+1];
    }
    L[n1] = INT_MAX;
    R[n2] = INT_MAX;
    i = 0;
    j = 0;
    for (k = p; k <=r; k++){
        if(L[i] < R[j]){
            A[k] = L[i];
            i++;
        }else{
            A[k] = R[j];
            j++;
        }
    }
}

void MergeSort(int A[],int p, int r){
    if(p < r){
        int q = (p+r)/2;
        MergeSort(A,p,q);
        MergeSort(A,q+1,r);
        Merge(A,p,q,r);
    }
}
int main(){
    int arr[10] = {56,389,67,34,498,23,45,67,57,457};
    MergeSort(arr,0,9);
    for(int i = 0; i < 10;i++){
        cout << arr[i]<< " ";
    }
    cout << endl;
    return 0;
}